package com.duoduo.sort;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @program: algorithm
 * @description: 最小的k个数
 * @author: chaidl  ！
 * @create: 2022-03-10 19:29
 */
public class 最小的k个数 {
    //直接排序
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] array = new int[k];
        Arrays.sort(arr);
        for (int i = 0; i < k; ++i) {
            array[i] = arr[i];
        }
        return array;
    }
    //使用大顶堆或者小顶堆
    public int[] getLeastNumbers2(int[] arr, int k) {
        //首先定义一个数组用于返回前k个数字
        int[] array = new int[k];
        if (k> arr.length || arr.length==0||k==0){
            return array;
        }
        //使用java自带的大跟堆类
        PriorityQueue<Integer> queue=new PriorityQueue<Integer>((v1,v2)->v2-v1);
        //将前k个数字添加到大跟堆里面
        for (int i = 0;i<k;i++){
            queue.offer(arr[i]);
        }
        //将第k个数字一次往大跟堆里面放，如果当前数字大于根，则跳过，小于就重新维护
        for (int i = k;i<arr.length;i++){
            if (queue.peek()>arr[i]){
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        //从大跟堆里面依次取出
        for (int i = 0;i<k;i++){
            array[i]=queue.poll();
        }
        return array;
    }
}
